package com.xuxiang.cloud.java.defcode.sort;

/**
 * @author xuxiang 2018/10/25 16:42
 */
public class TreeSort implements Sort {
    private void adjust(int [] arr, int from, int to, int pos) {
        int len = to - from +1;
        int p = pos - from + 1;
        int lp = p << 1;
        int rp = lp + 1;
        int maxp = p;
        if (lp <= len && arr[maxp + from - 1] < arr[lp + from - 1]) {
            maxp = lp;
        }
        if (rp <= len && arr[maxp + from - 1] < arr[rp + from -1 ]) {
            maxp = rp;
        }
        if (maxp != p) {
            swap(arr, maxp + from -1, p + from -1);
            adjust(arr, from, to, maxp + from - 1);
        }
    }

    private void createHeap(int [] arr, int from, int to) {
        int len = to - from + 1;
        for (int i = len >> 1; i > 0; i--) {
            adjust(arr, from, to, i + from - 1);
        }
    }

    @Override
    public void sort(int [] arr, int from, int to) {
        createHeap(arr, from, to);
        int len = to - from + 1;
        for (int i = 1; i < len; i++) {
            swap(arr, from, to - i + 1);
            adjust(arr, from, to - i, from);
        }
    }

    private void swap(int [] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
